package com.bee.剑指offer;

/**
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
 * 输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
 */
public class 数组中的逆序对 {

    /**
     * 暴力破解
     * 时间复复杂度太高，n^2不太适用
     */
    public static int InversePairs(int[] array) {
        int count = 0;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    count = (count + 1) % 1000000007;
                }
            }
        }
        return count;
    }

    /**
     * 使用归并排序
     */
    public static int InversePairs2(int[] array) {

        chifenData(array, 0, array.length - 1);
        return count;
    }

    public static void chifenData(int[] array, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        // 左子数组
        chifenData(array, low, mid);
        // 右子数组
        chifenData(array, mid + 1, high);
        mergerSort(array, low, mid, high);
    }

    // 记录有序对的总数
    private static int count = 0;

    // 合并
    private static void mergerSort(int[] array, int low, int mid, int high) {
        // 第一个子数组的起始位置
        int i = low;
        //  第二个子数组的起始位置
        int j = mid + 1;

        int[] temp = new int[high - low + 1];
        int index = 0;
        while (i <= mid && j <= high) {
            if (array[i] < array[j]) {
                temp[index] = array[i];
                i++;
            } else {
                temp[index] = array[j];
                // 只要出现左边的数组中的i位置的数据大于右边数组中的j数据，
                // 则认为左边数组中i元素后面的数据都大于右边数组中j数据，由于合并之后的子数组中的元素都是有序的
                count += mid - i + 1;
                count %= 1000000007;
                j++;
            }
            index++;
        }
        while (i <= mid) {
            temp[index] = array[i];
            i++;
            index++;
        }
        while (j <= high) {
            temp[index] = array[j];
            j++;
            index++;
        }
        for (int k = 0; k < temp.length; k++) {
            array[low + k] = temp[k];
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{1, 2, 3, 4, 5, 6, 7, 0};
        int count = InversePairs2(array);
        System.out.println(count);
    }
}
